{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #山脉数组的峰顶索引"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: peakIndexInMountainArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #山脉数组的峰顶索引"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>符合下列属性的数组 <code>arr</code> 称为 <strong>山峰数组</strong>（<strong>山脉数组）</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>arr.length &gt;= 3</code></li>\n",
    "\t<li>存在 <code>i</code>（<code>0 &lt; i&nbsp;&lt; arr.length - 1</code>）使得：\n",
    "\t<ul>\n",
    "\t\t<li><code>arr[0] &lt; arr[1] &lt; ... arr[i-1] &lt; arr[i] </code></li>\n",
    "\t\t<li><code>arr[i] &gt; arr[i+1] &gt; ... &gt; arr[arr.length - 1]</code></li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>给定由整数组成的山峰数组 <code>arr</code> ，返回任何满足 <code>arr[0] &lt; arr[1] &lt; ... arr[i - 1] &lt; arr[i] &gt; arr[i + 1] &gt; ... &gt; arr[arr.length - 1]</code> 的下标 <code>i</code>&nbsp;，即山峰顶部。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [0,1,0]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,3,5,4,2]\n",
    "<strong>输出：2</strong>\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [0,10,5,2]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [3,4,5,1]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [24,69,100,99,79,78,67,36,26,19]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= arr.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= arr[i] &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li>题目数据保证 <code>arr</code> 是一个山脉数组</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>很容易想到时间复杂度 <code>O(n)</code> 的解决方案，你可以设计一个 <code>O(log(n))</code> 的解决方案吗？</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 852&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/peak-index-in-a-mountain-array/\">https://leetcode-cn.com/problems/peak-index-in-a-mountain-array/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [B1IidL](https://leetcode.cn/problems/B1IidL/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [B1IidL](https://leetcode.cn/problems/B1IidL/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1,0]', '[0,2,1,0]', '[0,10,5,2]', '[3,4,5,1]', '[24,69,100,99,79,78,67,36,26,19]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = len(arr) - 1\n",
    "        while left<right:\n",
    "            mid=int((left+right)/2)\n",
    "            if arr[mid]>arr[mid+1]:\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        l, r = 0, len(arr)-1\n",
    "        while l < r:\n",
    "            mid = (l+r) // 2\n",
    "            if arr[mid] > arr[mid-1] and arr[mid] > arr[mid+1]:\n",
    "                return mid\n",
    "            elif arr[mid] < arr[mid+1]:\n",
    "                l = mid + 1\n",
    "            elif arr[mid] < arr[mid-1]:\n",
    "                r = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        for i in range(1, len(arr) - 1):\n",
    "            if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        return arr.index(max(arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        l, r,n = 0, len(arr), len(arr)\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if arr[mid] > arr[mid-1] and arr[mid] > arr[mid+1]:\n",
    "                return mid\n",
    "            if arr[mid-1] < arr[mid]:\n",
    "                l = mid \n",
    "            else:\n",
    "                r = mid\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        h = []\n",
    "        for i, val in enumerate(arr):\n",
    "            heapq.heappush(h, (-val, i))\n",
    "        return h[0][1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        def bisect(i, j):\n",
    "            if j - i <= 1:\n",
    "                if arr[i] < arr[j]:\n",
    "                    return j\n",
    "                else:\n",
    "                    return i\n",
    "\n",
    "            mid = (i + j) // 2\n",
    "            if arr[mid] >= arr[i] and arr[mid] >= arr[j]:\n",
    "                left = bisect(i, mid)\n",
    "                right = bisect(mid, j)\n",
    "                if arr[left] < arr[right]:\n",
    "                    return right\n",
    "                else:\n",
    "                    return left\n",
    "            elif arr[mid] < arr[j]:\n",
    "                return bisect(mid, j)\n",
    "            else:\n",
    "                return bisect(i, mid)\n",
    "        \n",
    "        return bisect(0, len(arr) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        prev = -1\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] < prev:\n",
    "                return i - 1\n",
    "            prev = arr[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "\n",
    "        left = 1\n",
    "        right = len(arr)-2\n",
    "        ans = 0\n",
    "\n",
    "        \n",
    "\n",
    "        while left<=right:\n",
    "            mid = (right+left)//2\n",
    "            \n",
    "            if arr[mid]>arr[mid+1]:\n",
    "                \n",
    "                right-=1\n",
    "            else:\n",
    "                left +=1\n",
    "        ans = left\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        start, end = 0, n - 1\n",
    "\n",
    "        while start + 1 < end:\n",
    "            mid = (start + end) // 2\n",
    "            if self.is_top(arr, mid):\n",
    "                return mid\n",
    "            if self.is_upward(arr, mid):\n",
    "                start = mid\n",
    "            else:\n",
    "                end = mid\n",
    "        \n",
    "        if self.is_top(arr, start):\n",
    "            return start\n",
    "        if self.is_top(arr, end):\n",
    "            return end\n",
    "        return -1\n",
    "    \n",
    "    def is_upward(self, arr, index):\n",
    "        if index == 0:\n",
    "            return True\n",
    "        if index == len(arr) - 1:\n",
    "            return False\n",
    "        if arr[index - 1] < arr[index] < arr[index + 1]:\n",
    "            return True\n",
    "        return False\n",
    "    \n",
    "    def is_top(self, arr, index):\n",
    "        if index == 0 or index == len(arr) - 1:\n",
    "            return False\n",
    "        if arr[index - 1] < arr[index] > arr[index + 1]:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        return arr.index(max(arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left, right, ans = 1, n - 2, 0\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] > arr[mid + 1]:\n",
    "                ans = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        for idx in range(1,len(arr)):\n",
    "            if arr[idx] < arr[idx - 1]:\n",
    "                return idx - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left, right, ans = 1, n-2, 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] > arr[mid + 1]:\n",
    "                ans = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = len(arr) - 1\n",
    "        while left <= right:\n",
    "            mid = (left + right) >> 1\n",
    "            if arr[mid] < arr[mid - 1]:\n",
    "                right = mid\n",
    "            elif arr[mid] < arr[mid + 1]:\n",
    "                left = mid\n",
    "            else:\n",
    "                return mid\n",
    "        return left - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        ans = -1\n",
    "\n",
    "        for i in range(1, n - 1):\n",
    "            if arr[i] > arr[i + 1]:\n",
    "                ans = i\n",
    "                break\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        return arr.index(max(arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        # for i in range(1,len(arr)-1):\n",
    "        #     if arr[i-1]<arr[i] and arr[i]>arr[i+1]:\n",
    "        #         return i \n",
    "        # return -1\n",
    "        #二分查找\n",
    "        l,r=0,len(arr)-1\n",
    "        while l<r:#二分，注意点，一是这里\n",
    "            # mid=(l+r)//2\n",
    "            mid=(l+r)>>1\n",
    "            if arr[mid]<arr[mid+1]:#二是判断条件\n",
    "                l=mid+1\n",
    "            else:r=mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left, right, ans = 0, len(arr)-2, 0\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2\n",
    "            if arr[mid] > arr[mid+1]:\n",
    "                ans = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left, right, ans = 1, len(arr)-2, 0\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2\n",
    "            if arr[mid] > arr[mid+1]:\n",
    "                ans = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        i, j = 1, n-2\n",
    "        while i <= j:\n",
    "            mid =(i+j) >> 1\n",
    "            if arr[mid] > arr[mid+1]:\n",
    "                j = mid - 1\n",
    "            else:\n",
    "                i = mid + 1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left, right, ans = 0, len(arr)-1, 0\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2\n",
    "            if arr[mid] > arr[mid+1]:\n",
    "                ans = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left, right = 0, len(arr) - 1\n",
    "        # because there must be a peak, so when left == right, it's the answer\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            # L--PEAK-MID---MID+1---R\n",
    "            if arr[mid] > arr[mid + 1]:\n",
    "                right = mid\n",
    "            elif arr[mid] < arr[mid + 1]:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        mid = len(arr) // 2\n",
    "        if len(arr) == 1:\n",
    "            return 0\n",
    "        if len(arr) == 2:\n",
    "            return 0 if arr[0] > arr[1] else 1\n",
    "        leftId = self.peakIndexInMountainArray(arr[:mid])\n",
    "        rightId = mid + self.peakIndexInMountainArray(arr[mid:])\n",
    "        return leftId if arr[leftId] > arr[rightId] else rightId        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        l,r = 1,len(arr)-2\n",
    "        while l<=r:\n",
    "            mid = (l+r)//2\n",
    "            if arr[mid]>arr[mid-1] and arr[mid]>arr[mid+1]:return mid\n",
    "            elif arr[mid]>arr[mid-1]:l=mid+1\n",
    "            else:r=mid-1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i]==max(arr):\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        l, r = 0, n-1\n",
    "        while l<= r:\n",
    "            mid = (l+r)//2\n",
    "            val = arr[mid]\n",
    "            if val > arr[mid-1] and val > arr[mid+1]:\n",
    "                return mid\n",
    "            elif val < arr[mid-1]:\n",
    "                r = mid-1\n",
    "            else:\n",
    "                l = mid+1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        # 二分查找\n",
    "        left, right = 0, len(arr) - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if arr[mid] >= arr[mid + 1]:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left, right = 0, len(arr) - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if arr[mid] > max(arr[mid - 1], arr[mid + 1]):\n",
    "                return mid\n",
    "            elif arr[mid] >= arr[mid + 1]:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        for i in range(0,len(arr)-1):\n",
    "            if arr[i]>arr[i+1]:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        if not arr:\n",
    "            return -1\n",
    "        n = len(arr)\n",
    "        start, end = 0, n - 1\n",
    "\n",
    "        while start + 1 < end:\n",
    "            mid = (start + end) // 2\n",
    "            if arr[mid - 1] < arr[mid] < arr[mid + 1]:\n",
    "                start = mid\n",
    "            elif arr[mid - 1] > arr[mid] > arr[mid + 1]:\n",
    "                end = mid\n",
    "            else:\n",
    "                return mid\n",
    "        \n",
    "        if arr[start - 1] < arr[start] > arr[start + 1]:\n",
    "            return start\n",
    "        return end\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        # 暴力遍历\n",
    "        # for i in range(1, len(arr) - 1):\n",
    "        #     if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:\n",
    "        #         return i\n",
    "\n",
    "        # 二分查找\n",
    "        left, right = 0, len(arr) - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if arr[mid] >= arr[mid + 1]:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        return arr.index(max(arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        ans = -1\n",
    "        \n",
    "        for i in range(1, n - 1):\n",
    "            if arr[i] > arr[i + 1]:\n",
    "                ans = i\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        #O(n)的解法\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i-1]<arr[i] and arr[i]>arr[i+1]:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        s = max(arr)\n",
    "        return arr.index(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        l = -1\n",
    "        r = len(arr)\n",
    "        while l + 1 != r:\n",
    "            m = floor((l + r) / 2)\n",
    "            if arr[m-1] < arr[m]:\n",
    "                l = m\n",
    "            else:\n",
    "                r = m\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        val = max(arr)\n",
    "        return arr.index(val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        i = arr.index(max(arr))\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left, right = 0, len(arr) - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if arr[mid] >= arr[mid + 1]:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        # 暴力遍历\n",
    "        # for i in range(1, len(arr) - 1):\n",
    "        #     if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:\n",
    "        #         return i\n",
    "\n",
    "        # 二分查找\n",
    "        left, right = 0, len(arr) - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if arr[mid] > arr[mid - 1] and arr[mid] > arr[mid + 1]:\n",
    "                return mid\n",
    "            elif arr[mid] > arr[mid - 1]:\n",
    "                left = mid + 1\n",
    "            elif arr[mid] > arr[mid + 1]:\n",
    "                right = mid - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        \n",
    "        left = 1\n",
    "        right = len(arr)-2\n",
    "        while left<=right:\n",
    "            mid = left+(right-left)//2\n",
    "            if arr[mid-1]<arr[mid]<arr[mid+1]:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid-1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        l, r = 0, len(arr) - 1\n",
    "        while l < r:\n",
    "            m = (l + r) // 2\n",
    "            if arr[m] < arr[m+1]:\n",
    "                l = m + 1\n",
    "            elif arr[m] > arr[m+1]:\n",
    "                if arr[m] >= arr[m-1]:\n",
    "                    return m\n",
    "                else:\n",
    "                    r = m - 1\n",
    "            else:\n",
    "                return m\n",
    "        return  r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        return arr.index(max(arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        # 暴力遍历\n",
    "        # for i in range(1, len(arr) - 1):\n",
    "        #     if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:\n",
    "        #         return i\n",
    "\n",
    "        # 二分查找\n",
    "        left, right = 0, len(arr) - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if arr[mid] > arr[mid - 1] and arr[mid] > arr[mid + 1]:\n",
    "                return mid\n",
    "            elif arr[mid] > arr[mid - 1]:\n",
    "                left = mid + 1\n",
    "            elif arr[mid] > arr[mid + 1]:\n",
    "                right = mid - 1\n",
    "        return mid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        for i in range(len(arr) - 1):\n",
    "            if arr[i+1] < arr[i]:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        L, R = 1, len(arr) - 2\n",
    "        while L <= R:\n",
    "            mid = (L + R) // 2\n",
    "            if arr[mid+1] > arr[mid]:\n",
    "                L = mid + 1\n",
    "            else:\n",
    "                R = mid - 1\n",
    "        return L "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left = 1\n",
    "        right = len(arr) - 2\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] > arr[mid - 1] and arr[mid] > arr[mid + 1]:\n",
    "                return mid\n",
    "            elif arr[mid] > arr[mid - 1]:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left, right, ans = 1, n - 2, 0\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] > arr[mid + 1]:\n",
    "                ans = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left, right = 1, len(arr)-2\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2\n",
    "            if arr[mid] > arr[mid+1]:\n",
    "                ans = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        l, r = 0, n - 1\n",
    "        ans = 0\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if arr[mid] < arr[mid + 1]:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        return arr.index(max(arr))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "      if not arr: return -1\n",
    "      \n",
    "      left, right = 0, len(arr) - 1\n",
    "      while left + 1 < right:\n",
    "        mid = (left + right) // 2\n",
    "        if arr[mid] < arr[mid + 1]: left = mid\n",
    "        else: right = mid\n",
    "      if arr[left] > arr[right]: left\n",
    "      return right\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left, right, ans = 1, n - 2, 0\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] > arr[mid + 1]:\n",
    "                ans = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        res = 0\n",
    "        for i in range(n-1):\n",
    "            if arr[i] > arr[i+1]:\n",
    "                return i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        for i in range(1,len(arr)-1):\n",
    "            if arr[i] > arr[i-1] and arr[i] > arr[i+1]:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr) -> int:\n",
    "        left=0\n",
    "        right=len(arr)-1\n",
    "        while left<=right:\n",
    "            mid=int((left+right)/2)\n",
    "            if arr[mid]>arr[mid-1] and arr[mid]>arr[mid+1]:\n",
    "                return mid\n",
    "            elif arr[mid]<arr[mid+1]:\n",
    "                left=mid+1\n",
    "            elif arr[mid]<arr[mid-1]:\n",
    "                right=mid-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        l, r = 0, len(arr) - 1\n",
    "        m = 0\n",
    "        while l <= r:\n",
    "            m = (l + r) // 2\n",
    "            if arr[m] < arr[m+1]:\n",
    "                l = m + 1\n",
    "            elif arr[m] > arr[m+1]:\n",
    "                if arr[m] >= arr[m-1]:\n",
    "                    return m\n",
    "                else:\n",
    "                    r = m - 1\n",
    "            else:\n",
    "                return m\n",
    "        return  m\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "#         ans = -1\n",
    "        \n",
    "#         for i in range(1, n - 1):\n",
    "#             if arr[i] > arr[i + 1]:\n",
    "#                 ans = i\n",
    "#                 break\n",
    "#         return ans\n",
    "        l, r , ans = 1, n - 2, 0\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if arr[mid] > arr[mid + 1]:\n",
    "                ans = mid\n",
    "                r = mid  - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        i, j = 1, n-2\n",
    "\n",
    "        while i<=j:\n",
    "            m = (i+j)//2\n",
    "            if arr[m] > arr[m-1] and arr[m] > arr[m+1]:\n",
    "                return m\n",
    "            elif arr[m-1] < arr[m] < arr[m+1]:\n",
    "                i = m+1\n",
    "            elif arr[m-1] > arr[m] > arr[m+1]:\n",
    "                j = m-1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left=0\n",
    "        right=len(arr)-1\n",
    "        \n",
    "        while left<right:\n",
    "            mid=(right-left)//2+left\n",
    "\n",
    "            if arr[mid]<arr[mid+1]:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left = 1\n",
    "        right = len(arr) - 2\n",
    "        mid = left + (right - left)//2\n",
    "        while left <= right:\n",
    "            if arr[mid-1] <= arr[mid] <= arr[mid+1]:\n",
    "                left = mid + 1\n",
    "            elif arr[mid-1] >= arr[mid] >= arr[mid+1]:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                return mid\n",
    "            mid = left + (right - left)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        for i in range(len(arr)-1):\n",
    "            if arr[i]>arr[i+1]:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        max_height = 0\n",
    "        max_height_idx = 0\n",
    "        for idx, height in enumerate(arr):\n",
    "            if height > max_height:\n",
    "                max_height = height\n",
    "                max_height_idx = idx\n",
    "        return max_height_idx\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        left = 1\n",
    "        right = len(arr) - 2\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] > arr[mid - 1] and arr[mid] > arr[mid + 1]:\n",
    "                return mid\n",
    "            elif arr[mid] > arr[mid - 1]:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        l = 0\n",
    "        r = n - 2\n",
    "        while(l <= r):\n",
    "            mid = (l+r) // 2\n",
    "            if arr[mid] >= arr[mid+1]:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        \n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        l = 0\n",
    "        r = len(arr) - 1\n",
    "        while l + 1 < r:\n",
    "            m = (l + r) // 2\n",
    "            if m - 1 < 0 or m + 1 >= len(arr):\n",
    "                return m\n",
    "            if arr[m] < arr[m - 1]:\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "        return l if arr[l] > arr[r] else r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        method = 'mine'\n",
    "        if method == 'mine':\n",
    "            l, r = 0, len(arr) - 1\n",
    "            while l <= r:\n",
    "                m = (l + r) // 2\n",
    "                if arr[m - 1] < arr[m] and arr[m] > arr[m + 1]:\n",
    "                    return m\n",
    "                elif arr[m - 1] < arr[m] < arr[m + 1]:\n",
    "                    l = m + 1\n",
    "                elif arr[m - 1] > arr[m] > arr[m + 1]:\n",
    "                    r = m - 1\n",
    "            return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        for i in range(1, len(arr) - 1):\n",
    "            if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        s, e = 0, len(arr)-1\n",
    "        while s <= e:\n",
    "            m = (s+e)//2\n",
    "            if arr[m] > arr[m+1]:\n",
    "                e = m - 1\n",
    "            elif arr[m] < arr[m+1]:\n",
    "                s = m + 1\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, arr: List[int]) -> int:\n",
    "        if not arr: return -1\n",
    "        \n",
    "        left, right = 0, len(arr) - 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if (arr[mid] < arr[mid + 1]): left = mid\n",
    "            else: right = mid\n",
    "        if (arr[left] > arr[left - 1] and arr[left] > arr[left + 1]): return left\n",
    "        if (arr[right] > arr[right - 1] and arr[right] > arr[right + 1]): return right\n",
    "        return -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
